package cn.edu.zufe.mjt.dfs;

import java.util.*;

/**
 * 题目描述:
 * 给定一棵 n 个节点的树，节点编号为1-n，树的根节点固定为 1。我们有两种方式表示树的结构:
 * 1.方式一:通过 n-1 条边的形式，每条边 uv 表示节点 u 和节点 v 之间存在一条边。
 * 2.方式二:通过一个 father 数组， father[i]表示节点 i+1 的父节点。
 * 请你编写程序，读入树的结构并使用 深度优先搜索 遍历打印这棵树的节点编号。
 * 为了输出统一，从根节点开始遍历，优先访问序号小的子节点
 * 输入:
 * 输入包含三部分
 * 1.第一行包含一个整数 n，表示树的节点个数。
 * 2.第二行包含一个整数 type ，表示树的表示方式!
 *      如果 type =1，表示通过边的形式输入。
 *      如果 type =2，表示通过 father 数组输入。
 * 3.如果 type =1，接下来会有 n-1 行，每行两个整数 uv，表示树中节点 u 和节点v之间存在一条边。
 * 4.如果 type =2，接下来一行有n个整数，father[i]表示节点 i+1 的父节点，其中 father[0] = 0，表示1号节点为根节点,没有父节点。
 * 输出:
 * 打印遍历这棵树的节点编号
 */
public class TraversalOfTree {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int type = sc.nextInt();
        if (type == 1) {
            List<List<Integer>> edges = new ArrayList<>(); // 存储边的形式
            for (int i = 0; i < n; i++) {
                edges.add(new ArrayList<>());
            }
            for (int i = 0; i < n - 1; i++) {
                int u = sc.nextInt();
                int v = sc.nextInt();
                edges.get(u - 1).add(v);
                edges.get(v - 1).add(u);
            }
            // 深度优先搜索遍历
            edgesDfs(1, edges, 0);
        } else if (type == 2) {
            int[] father = new int[n];
            for (int i = 0; i < n; i++) {
                father[i] = sc.nextInt();
            }
            // 构造邻接表
            List<List<Integer>> adj = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                adj.add(new ArrayList<>());
            }
            for (int i = 1; i < n; i++) {
                adj.get(father[i] - 1).add(i);
            }
            // 深度优先搜索遍历
            edgesDfs(1, adj, 0);
        }
    }

    public static void edgesDfs(int v, List<List<Integer>> edges, int father) {
        List<Integer> list = edges.get(v - 1);  // 获取节点 v 的所有邻居
        Collections.sort(list); // 排序
        for (Integer to : list) {
            if (to != father) {  // 判断边中是否包含父节点
                edgesDfs(to, edges, v);  // 递归遍历子节点
            }
        }
        System.out.print(v + " ");
    }

}
